package com.husk.leetcode.listnode;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@foxmail.com
 * @since 2021/7/22
 */
public class Solution {
    Map<Node, Node> cachedNode = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = this.copyRandomList(head.next);
            headNew.random = this.copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode prev = new ListNode(head.val);
        while (head.next != null) {
            ListNode node = new ListNode(head.next.val);
            node.next = prev;
            prev = node;
            head = head.next;
        }
        return prev;
    }

    /**
     * 删除链表的节点
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        if (pre.val == val) {
            return pre.next;
        }
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if (cur != null) {
            pre.next = cur.next;
        }
        return head;
    }


    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> list = new LinkedList<>();
        while (head != null) {
            list.addFirst(head.val);
            head = head.next;
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    /**
     * 链表的倒数第k个节点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode node = head;
        for (int i = 0; i < k; i++) {
            node = node.next;
        }
        while (node != null) {
            node = node.next;
            head = head.next;
        }
        return head;
    }

    /**
     * 面试题 02.08. 环路检测
     * https://leetcode-cn.com/problems/linked-list-cycle-lcci/
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            boolean result = set.add(node);
            if (!result) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public int compareVersion(String version1, String version2) {
        List<Integer> v1 = Arrays.stream(version1.split("\\.")).map(Integer::valueOf).collect(Collectors.toList());
        List<Integer> v2 = Arrays.stream(version2.split("\\.")).map(Integer::valueOf).collect(Collectors.toList());

        for (int i = 0; i < v1.size() || i < v2.size(); i++) {
            if (i > v1.size() - 1 && v2.get(i) >= 0) {
                if (v2.get(i) == 0) {
                    continue;
                }
                return -1;
            } else if (i > v2.size() - 1 && v1.get(i) >= 0) {
                if (v1.get(i) == 0) {
                    continue;
                }
                return 1;
            } else if (v1.get(i).equals(v2.get(i))) {
                continue;
            } else {
                return v1.get(i) > v2.get(i) ? 1 : -1;
            }
        }
        return 0;
    }

    @Test
    public void test() {
        this.compareVersion("1.0", "1.0.0");
    }


}
